package stu.day39_day.day40;

import java.util.Arrays;

public class hw4 {

    public int bestSeqAtIndex(int[] height, int[] weight) {
        int len = height.length;
        int[][] arr = new int[len][2];
        for (int i = 0; i < len; i++) {
            arr[i][0] = height[i];
            arr[i][1] = weight[i];
        }
        Arrays.sort(arr,(a,b)-> a[0]==b[0]?b[1]-a[1]:a[0]-b[0] );
        return dp(arr);
    }

    public static int dp(int[][] arr){
        int len =arr.length;
        int[] dp = new int[len];
        Arrays.fill(dp,1);
        int max = 0;
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(arr[i][1]>arr[j][1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    public int bestTeamScore(int[] height, int[] weight) {
        int len  = weight.length;
        int[][] arr = new int[len][2];
        for (int i = 0; i < len; i++) {
            arr[i][0] = height[i];
            arr[i][1] = weight[i];
        }
        Arrays.sort(arr,(a,b)-> a[0]==b[0]?b[1]-a[1]:a[0]-b[0]);

        int[] dp = new int[len];

        int max = 0;
        for (int i = 0; i < len; i++) {
           int num = hs(dp,arr[i][1]);
           if(num==max){
               max += 1;
               dp[max] = arr[i][1];
           }else {
               dp[num] = arr[i][1];
           }
        }

        return max;



    }
   public int hs(int[] dp,int num){
        int left = 0;
        int right = dp.length;
        while(left<right){
            int mid = (left+right)/2;
            if(dp[mid]>=num){
                right = mid;
            }else {
                left = mid+1;
            }
        }
        return left;
   }




}
